package leetcode;

/**
 * 预测赢家
 * f(x,y)= max(f(x+2,y)+a[x] , f(x+1,y-1)+a[x] ) ,max(f(x,y-2)+a[y] , f(x+1,y-1)+a[y] ) ,
 */
public class T486 {
    public static void main(String[] args) {
        int[] nums = {1,5,2};

        T486 t486 = new T486();
        t486.PredictTheWinner(nums);
    }

    public boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for(int n : nums)
            sum += n;
        int first = f(nums, 0, nums.length-1);
        System.out.println(first);
        return first >= (sum - first);
    }

    //    public boolean PredictTheWinner(int[] nums) {
//        int max1 = f(0, nums.length - 1, nums);
//        System.out.println(max1);
//        return true;
//    }


    private int f(int[] nums, int i, int j) {
        if(i == j)
            return nums[i];
        if(i+1 == j)
            return Math.max(nums[i], nums[j]);

        // 都是聪明人，你如果想要赢实际上就是你在选更大数字的时候，同时要保证留给对方更小的数字
        return Math.max(
                nums[i] + Math.min(f(nums, i+1, j-1), f(nums, i+2, j)),
                nums[j] + Math.min(f(nums, i+1, j-1), f(nums, i, j-2)));
    }


    public static int f(int x,int y,int[] nums){
        if(x<0||x>y||y>=nums.length){
            return 0;
        }
        if(y==x){
            return nums[x];
        }else if(y-x ==1){
            return Math.max(nums[x], nums[y]);
        }

        int pickX = Math.max(f(x+2,y,nums),f(x+1,y-1,nums))+nums[x];
        int pickY = Math.max(f(x+1,y-1,nums),f(x,y-2,nums))+nums[y];
        return Math.max(pickX, pickY);

    }

}
